package com.leetcode.algorithm.y22.m06;

/**
 * 1567. 乘积为正数的最长子数组长度
 * 
 * https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/
 * 
 * @author jie.deng
 *
 */
class Question1567Solution01 {

	public int getMaxLen(int[] nums) {
		int maxLen = 0;
		int len = nums.length;
		// 上一个等于0的元素的索引
		int prevZeroidx = -1;
		// 区间nums[i...j](nums[i]=0,nums[j]=0)内第一个负数的索引
		int firstNegativeidx = -1;
		// 区间nums[i...j](nums[i]=0,nums[j]=0)内最后一个负数的索引
		int lastNegativeidx = -1;
		// 区间nums[i...j](nums[i]=0,nums[j]=0)内负数的个数
		int cntOfNegative = 0;
		for (int i = 0; i < len; i++) {
			if (nums[i] == 0) {
				if (cntOfNegative % 2 == 0) {
					// 区间所有
					maxLen = Math.max(maxLen, i - prevZeroidx - 1);
				} else {
					// 去掉第一个负数以及之前的正数
					maxLen = Math.max(maxLen, i - firstNegativeidx - 1);
					// 去掉最后一个负数以及之后的正数
					maxLen = Math.max(maxLen, lastNegativeidx - prevZeroidx - 1);
				}
				cntOfNegative = 0;
				firstNegativeidx = -1;
				lastNegativeidx = -1;
				prevZeroidx = i;
			} else if (nums[i] < 0) {
				cntOfNegative++;
				if (firstNegativeidx == -1) {
					firstNegativeidx = i;
				}
				lastNegativeidx = i;
			}
		}
		if (nums[len - 1] != 0) {
			if (cntOfNegative % 2 == 0) {
				// 区间所有
				maxLen = Math.max(maxLen, len - prevZeroidx - 1);
			} else {
				if (nums[len - 1] > 0) {
					maxLen = Math.max(maxLen, len - firstNegativeidx - 1);
					maxLen = Math.max(maxLen, lastNegativeidx - prevZeroidx - 1);
				} else {
					// 不要最后一个负数
					maxLen = Math.max(maxLen, len - 2 - prevZeroidx);
				}
			}
		}
		return maxLen;
	}

}